1. Field of the Invention
The present invention relates to data communications, and, in particular, to switch fabrics for routing packets of user data between multiple sources and destinations.
2. Description of the Related Art
FIG. 1 shows a block diagram of a prior-art three-stage switch fabric 100 for data communications. In particular, switch fabric 100 routes packets of user data received from one or more sources 102 towards one or more destinations 110. Switch fabric 100 comprises an input stage 104, a switching stage 106, and an output stage 108. Input stage 104 is configured to receive the packets of user data from sources 102, divide each packet of user data into one or more cells of user data, and transmit the cells of user data to switching stage 106. Switching stage 106 is configured to route the cells of user data received from input stage 104 to output stage 108. Output stage 108 is configured to assemble the cells of user data received from switching stage 106 into re-assembled packets of user data and transmit the re-assembled packets of user data to destinations 110.
In non-blocking switch fabrics, user data received from any particular source 102 can be routed through switch fabric 100 to any particular destination 110, independent of whether any other user data is being routed from one or more other sources towards one or more other destinations through switch fabric 100. When packets of user data transmitted from the sources are received at an input port of input stage 104, the user data is buffered for eventual transmission through switching stage 106 to output stage 108, where the routed user data is again buffered for eventual transmission to the destination via an output port of the output stage associated with that destination.
To perform these data buffering functions, input stage 104 and output stage 108 are both configured with a number of different routing queues (e.g., designated memory locations) in which the user data are temporarily stored. In prior art switch fabrics, such as switch fabric 100 of FIG. 1, there is a one-to-one relationship between the input ports and the routing queues in the input stage. In other words, all user data arriving at a particular input port is stored in a single routing queue, and all user data stored in a particular routing queue arrives at a single input port. Similarly, there is a one-to-one relationship between the routing queues in the input stage and the routing queues in the output stage. In other words, all user data that is stored in a particular routing queue in the input stage is routed to a single routing queue in the output stage, and all user data is stored in a particular routing queue in the output stage is routed from a single routing queue in the input stage. On the other hand, there is a many-to-one relationship between routing queues and output ports in the output stage. In other words, all user data that is stored in a particular set of one or more routing queues in the output stage is transmitted via a single output port, and all user data that is transmitted via a particular output port is routed from a single set of one or more routing queues in the output stage. The logical associations between input ports and routing queues in the input stage and between routing queues and output ports in the output stage are determined by the physical locations of (i.e., physical connections between) the various devices for form the input and output stages.
The input stage is implemented with a scheduler that is responsible for determining when to transmit data from the various queues in the input stage to the switching stage for routing. When the scheduler determines that a particular queue is to be serviced (i.e., have user data transmitted to the switching stage), a bid (i.e., service request) is transmitted from the input stage (e.g., encoded in the header of a cell carrying other user data in its payload) to a bid arbitrator implemented as part of the switching stage. The bid arbitrator determines whether to accept (i.e., grant) or reject (i.e., deny) the bid received from the input stage. A message is transmitted from the switching stage back to the input stage identifying whether the bid was accepted or rejected. If a bid is accepted, then a connection is eventually established within the switching stage for routing the user data associated with that granted bid. In response to receiving a granted bid message, user data is transmitted from the queue in the input stage to the switching stage for routing through the corresponding connection to the appropriate queue in the output stage.
In prior art switch fabrics, such as switch fabric 100 of FIG. 1, each bid received from the input stage is considered by the bid arbitrator in the switching stage only once, with the bid being either accepted or rejected. If a bid is rejected, then the input stage must transmit a subsequent bid for servicing the same queue to the switching stage for consideration by the bid arbitrator. Individual bids will continue to be transmitted and considered until the bid arbitrator finally accepts one for servicing that queue.
Depending on the implementation, a bid arbitrator implemented in the switching stage may use different types of information in determining whether to accept or reject a particular bid. For example, a bid arbitrator may rely on “fairness” when considering a particular bid, where “fairness” relates to the notion of equitably sharing over time the resources of the switching stage among all of the different queues in the input stage that desire service. In addition, a bid arbitrator of the prior art might be designed to take into account the status of the various queues in the output stage. In particular, if a particular queue in the output stage is currently full, then a bid arbitrator may use that information (which is transmitted from the output stage to the switching stage) to reject a current bid for service that would result in even more user data being transmitted to that queue.